#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define N 20

void bubble_sort(int arr[], int n);
void select_sort(int arr[], int n);
void insert_sort(int arr[], int n);
int main(int argc, char *argv[])
{
	int arr[N] = {0};
	srand(time(NULL));

	for(int i = 0; i < N; i++){
		arr[i] = rand()%100;
		printf("%d ", arr[i]);
	}
	printf("\n\n");

	bubble_sort(arr, N);
	for(int i = 0; i < N; i++){
		printf("%d ", arr[i]);
	}
	printf("\n\n");

	select_sort(arr, N);
	for(int i = 0; i < N; i++){
		printf("%d ", arr[i]);
	}
	printf("\n\n");
	insert_sort(arr, N);
	for(int i = 0; i < N; i++){
		printf("%d ", arr[i]);
	}
	printf("\n\n");

	return 0;
}

void bubble_sort(int arr[], int n){
	int i, j;
	int tem;
	for(i = 0; i < n-1; i++){// 将后第i位归位
		for(j = 0; j < n-1-i; j++){
			if(arr[j] > arr[j+1]){//从小到大排
				tem = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tem;
			}
		}
	}
}

void select_sort(int arr[], int n){
	int i, j;
	int max;
	int tem;
	for(i = 0; i < n - 1; i++){// n-1趟，使n-1个有序
		max = i;
		for(j = i+1; j < N; j++){
			if(arr[max] < arr[j]){
				max = j;
			}
		}
		if(i !=max){
			tem = arr[i];
			arr[i] = arr[max];
			arr[max] = tem;
		}
	}	
}

void insert_sort(int arr[], int n){
	int i;
	int j;
	int tem;
	for(i = 1; i < n; i++){
		tem = arr[i];
		for(j = i-1 ; j >= 0; j--){
			if(tem < arr[j]){
				arr[j+1] = arr[j];
			}else{
				break;
			}
		}
		arr[j+1] = tem;
	}
}
